Basic Concepts of Mathematical Logic

1. What is a proposition or statement in mathematical logic?

A) A question that can be true or false
B) A command that has a specific meaning
C) A declarative sentence that is either true or false, but not both simultaneously
D) An exclamation that expresses a feeling

2. What is the truth value of a statement?

A) The numerical value of a mathematical expression
B) The meaning of a statement in everyday language
C) The truth or falsity of a statement
D) The complexity of a logical expression

3. Which of the following is NOT a proposition?

A) "One plus two equals three."
B) "Close the door."
C) "One plus two equals five."
D) "The sky is blue."

4. What are the possible truth values in two-valued logic?

A) True, False, and Unknown
B) Yes and No
C) True (T) and False (F)
D) Positive and Negative

5. What are the symbols used to denote propositional variables?

A) Symbols like &, |, ~
B) Numbers like 1, 2, 3
C) Letters such as p, q, r
D) Greek letters like α, β, γ

6. Which of the following statements is true about logical propositions?

A) A statement can be true and false at the same time.
B) A proposition is a type of question.
C) A proposition must have a clear truth value.
D) Exclamations are valid propositions in logic.

7. What is the term used to describe logic with only two possible truth values?

A) Multi-valued logic
B) Three-valued logic
C) Binary logic
D) Two-valued logic

8. Which of the following can be a valid propositional variable?

A) A complete sentence like "The Earth is round."
B) A symbol like +
C) A letter such as p or q
D) A numerical value like 5

9. What is the importance of studying logic in discrete mathematics?

A) It helps in solving complex calculus problems.
B) It provides the theoretical basis for areas like artificial intelligence and digital logic design.
C) It replaces the need for algebra.
D) It simplifies the study of biology.

10. Which of the following is true about questions and propositions?

A) Questions are always propositions.
B) Propositions are always questions.
C) Questions can sometimes be propositions.
D) Questions are not propositions.

11. What does the study of logic provide in the context of computer science?

A) Practical methods for performing arithmetic
B) Theoretical basis for areas such as artificial intelligence, digital logic, and design
C) A way to solve differential equations
D) Techniques for graphic design

12. Which of the following is a proposition?

A) "What is your name?"
B) "Stop talking!"
C) "It is raining outside."
D) "Wow, that's amazing!"

13. What type of sentence is a proposition?

A) Imperative
B) Exclamatory
C) Interrogative
D) Declarative

14. How is the truth value 'true' commonly denoted in symbolic logic?

A) F or 0
B) T or 1
C) + or -
D) Y or N

15. How is the truth value 'false' commonly denoted in symbolic logic?

A) F or 0
B) T or 1
C) + or -
D) Y or N

16. What is an atomic proposition?

A) A single propositional variable or constant
B) A proposition made of two or more statements
C) A statement that is always true
D) A type of compound proposition

17. What is a compound proposition?

A) A proposition that cannot be divided
B) A proposition obtained from combinations of other propositions using logical operators
C) A statement that is false
D) A type of negation

18. What are connectives in the context of logic?

A) Mathematical functions
B) Operators used to form compound propositions
C) Types of atomic propositions
D) Statements that are always true

19. Which of the following is NOT a basic connective?

A) Negation
B) Conjunction
C) Disjunction
D) Multiplication

20. Which symbol represents negation?

A) ∧
B) ∨
C) →
D) ~

21. Which symbol represents conjunction?

A) ∧
B) ∨
C) →
D) ~

22. Which symbol represents disjunction?

A) ∧
B) ∨
C) →
D) ↔

23. Which symbol represents conditional (implication)?

A) ∧
B) ∨
C) →
D) ↔

24. Which symbol represents biconditional?

A) ∧
B) ∨
C) →
D) ↔

25. If p: "The sky is blue," what is the negation of p?

A) The sky is blue
B) The sky is not blue
C) The sky is always blue
D) None of the above

26. What does the negation of a proposition do?

A) Makes a true proposition false
B) Combines two propositions
C) Always results in a true statement
D) Makes a false proposition true

27. Which statement about conjunction (p ∧ q) is true?

A) It is true only when both p and q are false
B) It is true only when either p or q is true
C) It is true only when both p and q are true
D) It is true when at least one of p or q is true

28. Which statement about disjunction (p ∨ q) is true?

A) It is true only when both p and q are true
B) It is true only when both p and q are false
C) It is true when at least one of p or q is true
D) It is false when either p or q is true

29. In a conditional statement p → q, when is it false?

A) When p is false and q is true
B) When p is true and q is false
C) When both p and q are true
D) When both p and q are false

30. Which of the following is a correct way to interpret p → q?

A) p is a necessary condition for q
B) q is a sufficient condition for p
C) p is sufficient for q
D) p is necessary and sufficient for q

31. When is the biconditional p ↔ q true?

A) When p is true and q is false
B) When both p and q are true, or both are false
C) When p is false and q is true
D) When both p and q are true only

32. What does p ↔ q mean?

A) p and q are both true
B) p is true only if q is true
C) p if and only if q
D) p or q, but not both

33. Which of the following is an example of a conjunction?

A) It is raining or it is sunny
B) It is raining and it is cold
C) If it is raining, then I will take an umbrella
D) If and only if it is raining, then it is cloudy

34. Which of the following is an example of a disjunction?

A) If it rains, I will stay home
B) It is raining and it is windy
C) It is raining or it is snowing
D) It is raining if and only if it is cloudy

35. Which of the following is an example of a conditional statement?

A) It is not raining
B) It is raining and it is cold
C) If it rains, then I will use an umbrella
D) It is raining or it is cold

36. What does a truth table show?

A) The logical operators used in a compound statement
B) The truth values of a compound proposition for all possible cases
C) The syntax of logical statements
D) The frequency of true values in a compound statement

Correct Answer: B) The truth values of a compound proposition for all possible cases.

37. How many possible cases are there for the conjunction of two propositions, p and q?

A) Two
B) Three
C) Four
D) Five

Correct Answer: C) Four.

38. What is the result of the conjunction p ∧ q when both p and q are true?

A) True
B) False
C) Undefined
D) Depends on the value of p

Correct Answer: A) True.

39. In a truth table for the conjunction p ∧ q, what is the truth value when p is true and q is false?

A) True
B) False
C) True if q is a negation
D) Undefined

Correct Answer: B) False.

40. In the context of truth tables, what does the symbol ∧ represent?

A) Disjunction (OR)
B) Conjunction (AND)
C) Negation (NOT)
D) Implication (IF)

Correct Answer: B) Conjunction (AND).

41. What is the truth value of p ∧ q when both p and q are false?

A) True
B) False
C) It cannot be determined
D) Depends on the operator used

Correct Answer: B) False.

42. Which table number represents the truth table for the conjunction of two propositions p and q?

A) Table 2.1.3
B) Table 2.1.4
C) Table 2.1.5
D) Table 2.1.6

Correct Answer: B) Table 2.1.4.

43. What does the negation operator do to the truth value of a proposition?

A) It makes it true
B) It keeps it unchanged
C) It makes it false
D) It inverts the truth value

Correct Answer: D) It inverts the truth value.

44. How many columns are typically needed in a truth table for a compound proposition involving two simple propositions, p and q?

A) Two
B) Three
C) Four
D) Five

Correct Answer: B) Three.

45. Which table number shows the truth table for the disjunction of two propositions?

A) Table 2.1.4
B) Table 2.1.5
C) Table 2.1.6
D) Table 2.1.7

Correct Answer: B) Table 2.1.5.

46. What is the converse of the conditional proposition p → q?

A) q → p
B) ~q → ~p
C) ~p → ~q
D) p → ~q

Correct Answer: A) q → p

47. What is the contrapositive of the conditional proposition p → q?

A) q → p
B) ~q → ~p
C) ~p → ~q
D) p → ~q

Correct Answer: B) ~q → ~p

48. What is the inverse of the conditional proposition p → q?

A) q → p
B) ~q → ~p
C) ~p → ~q
D) p → ~q

Correct Answer: C) ~p → ~q

49. Which of the following statements is logically equivalent to the contrapositive of p → q?

A) p → q
B) q → p
C) ~p → ~q
D) ~q → ~p

Correct Answer: A) p → q

50. If p represents "It rains" and q represents "The crops will grow," what does the statement ~p → ~q represent?

A) If it rains, then the crops will grow.
B) If it does not rain, then the crops will not grow.
C) If the crops do not grow, then it did not rain.
D) If the crops grow, then it rained.

Correct Answer: B) If it does not rain, then the crops will not grow.

51. Which statement correctly describes the contrapositive of the statement "If it rains, then the crops will grow"?

A) If the crops grow, then it rained.
B) If the crops do not grow, then it did not rain.
C) If it does not rain, then the crops will not grow.
D) If it rains, then the crops will grow.

Correct Answer: B) If the crops do not grow, then it did not rain.

52. What is the logical equivalent of the statement "If the crops grow, then it rained"?

A) Converse of p → q
B) Contrapositive of p → q
C) Inverse of p → q
D) Original proposition p → q

Correct Answer: A) Converse of p → q

53. If the proposition p → q is true, which of the following must also be true?

A) q → p
B) ~q → ~p
C) ~p → ~q
D) Both B and C

Correct Answer: B) ~q → ~p

54. If the inverse ~p → ~q is false, what can be inferred about p → q?

A) p → q is true
B) p → q is false
C) p → q is not affected
D) None of the above

Correct Answer: B) p → q is false

55. If "If it rains, then the crops will grow" is false, which of the following must also be false?

A) "If the crops grow, then it rained."
B) "If the crops do not grow, then it did not rain."
C) "If it does not rain, then the crops will not grow."
D) "It rains, and the crops do not grow."

Correct Answer: B) "If the crops do not grow, then it did not rain."

56. What is the negation of a conjunction ( p ∧ q )?

A) ( ¬ p ∧ ¬ q )
B) ( ¬ p ∨ ¬ q )
C) ( p ∨ q )
D) ( p ∧ q )

Correct Answer: B) ( ¬ p ∨ ¬ q )

57. What is the symbolic representation of the negation of a disjunction ( p ∨ q )?

A) ( ¬ p ∧ ¬ q )
B) ( ¬ p ∨ ¬ q )
C) ( ¬ (p ∨ q) )
D) ( p ∧ q )

Correct Answer: A) ( ¬ p ∧ ¬ q )

58. What is the negation of a negation ( ¬ (¬ p) )?

A) ( ¬ p )
B) ( p )
C) ( ¬ (¬ p) )
D) ( ¬ (¬ (¬ p)) )

Correct Answer: B) ( p )

59. How can the negation of a conditional statement ( p → q ) be expressed?

A) ( p → ¬ q )
B) ( ¬ p → q )
C) ( p ∧ ¬ q )
D) ( ¬ (p → q) )

Correct Answer: C) ( p ∧ ¬ q )

60. What is the symbolic representation of the negation of a bi-conditional statement ( p ↔ q )?

A) ( p ↔ ¬ q )
B) ( ¬ p ↔ q )
C) ( ¬ (p ↔ q) )
D) ( ¬ p ↔ ¬ q )

Correct Answer: C) ( ¬ (p ↔ q) )

61. Which of the following correctly represents ( ¬ (p ∧ q) )?

A) ( ¬ p ∧ ¬ q )
B) ( ¬ p ∨ ¬ q )
C) ( ¬ p → ¬ q )
D) ( p ∨ q )

Correct Answer: B) ( ¬ p ∨ ¬ q )

62. Which of the following represents ( ¬ (p ∨ q) )?

A) ( ¬ p ∧ ¬ q )
B) ( ¬ p ∨ ¬ q )
C) ( ¬ p → ¬ q )
D) ( p ∧ q )

Correct Answer: A) ( ¬ p ∧ ¬ q )

63. If ( p ↔ q ) is a bi-conditional statement, what is its negation?

A) ( p ↔ ¬ q )
B) ( ¬ p ↔ q )
C) ( ¬ (p ↔ q) )
D) ( p → q )

Correct Answer: C) ( ¬ (p ↔ q) )

64. Which statement is true about the negation of a statement ( p )?

A) ( ¬ (¬ p) ) is always false.
B) ( ¬ (¬ p) ) is equivalent to ( p ).
C) ( ¬ p ) is equivalent to ( ¬ (¬ p) ).
D) ( ¬ (¬ p) ) is always true.

Correct Answer: B) ( ¬ (¬ p) ) is equivalent to ( p )

65. Which truth table would represent the negation of a conditional statement ( p → q )?

A) The table where ( p → q ) is true when ( p ) is false or both ( p ) and ( q ) are true.
B) The table where ( p → q ) is true when ( p ) is true and ( q ) is true, and false otherwise.
C) The table where ( ¬ (p → q) ) is true only when ( p ) is true and ( q ) is false.
D) The table where ( ¬ (p → q) ) is true for all values of ( p ) and ( q ).

Correct Answer: C) The table where ( ¬ (p → q) ) is true only when ( p ) is true and ( q ) is false.

66. What does the Idempotent Law state?

A) 𝑝 ∨ 𝑞 ≡ 𝑞
B) 𝑝 ∧ 𝑞 ≡ 𝑞
C) 𝑝 ∨ 𝑞 ≡ 𝑝
D) 𝑝 ∧ 𝑞 ≡ 𝑝

Correct Answers: C) 𝑝 ∨ 𝑞 ≡ 𝑝 and D) 𝑝 ∧ 𝑞 ≡ 𝑝

67. Which of the following expressions correctly applies the Associative Law?

A) (𝑝 ∧ 𝑞) ∧ 𝑟 ≡ 𝑝 ∧ (𝑞 ∧ 𝑟)
B) 𝑝 ∧ (𝑞 ∧ 𝑟) ≡ (𝑝 ∧ 𝑞) ∧ 𝑟
C) (𝑝 ∨ 𝑞) ∧ 𝑟 ≡ 𝑝 ∧ (𝑞 ∧ 𝑟)
D) (𝑝 ∧ 𝑞) ∨ 𝑟 ≡ 𝑝 ∧ (𝑞 ∨ 𝑟)

Correct Answers: A) (𝑝 ∧ 𝑞) ∧ 𝑟 ≡ 𝑝 ∧ (𝑞 ∧ 𝑟) and B) 𝑝 ∧ (𝑞 ∧ 𝑟) ≡ (𝑝 ∧ 𝑞) ∧ 𝑟

68. Which of the following is an example of the Commutative Law?

A) 𝑝 ∨ (𝑞 ∧ 𝑟) ≡ (𝑝 ∧ 𝑞) ∨ (𝑝 ∧ 𝑟)
B) 𝑝 ∧ 𝑞 ≡ 𝑞 ∧ 𝑝
C) 𝑝 ∨ 𝑞 ≡ 𝑝 ∧ 𝑞
D) 𝑝 ∧ (𝑞 ∨ 𝑟) ≡ (𝑝 ∧ 𝑞) ∨ (𝑝 ∧ 𝑟)

Correct Answers: B) 𝑝 ∧ 𝑞 ≡ 𝑞 ∧ 𝑝 and C) 𝑝 ∨ 𝑞 ≡ 𝑞 ∨ 𝑝

69. What does the Distributive Law state?

A) 𝑝 ∧ (𝑞 ∨ 𝑟) ≡ (𝑝 ∧ 𝑞) ∨ (𝑝 ∧ 𝑟)
B) 𝑝 ∨ (𝑞 ∧ 𝑟) ≡ (𝑝 ∧ 𝑞) ∨ (𝑝 ∧ 𝑟)
C) 𝑝 ∨ (𝑞 ∧ 𝑟) ≡ (𝑝 ∨ 𝑞) ∧ (𝑝 ∨ 𝑟)
D) 𝑝 ∧ (𝑞 ∧ 𝑟) ≡ (𝑝 ∧ 𝑞) ∧ (𝑝 ∧ 𝑟)

Correct Answers: A) 𝑝 ∧ (𝑞 ∨ 𝑟) ≡ (𝑝 ∧ 𝑞) ∨ (𝑝 ∧ 𝑟) and C) 𝑝 ∨ (𝑞 ∧ 𝑟) ≡ (𝑝 ∨ 𝑞) ∧ (𝑝 ∨ 𝑟)

70. Which of the following is correct according to the Identity Law?

A) 𝑝 ∧ 𝑇 ≡ 𝑇
B) 𝑝 ∨ 𝐹 ≡ 𝑝
C) 𝑝 ∧ 𝐹 ≡ 𝑝
D) 𝑝 ∨ 𝑇 ≡ 𝑝

Correct Answers: B) 𝑝 ∨ 𝐹 ≡ 𝑝 and D) 𝑝 ∧ 𝑇 ≡ 𝑝

71. What does the Complement Law state?

A) 𝑝 ∨ ¬𝑝 ≡ 𝐹
B) 𝑝 ∧ ¬𝑝 ≡ 𝑇
C) ¬𝑇 ≡ 𝑇
D) 𝑝 ∨ ¬𝑝 ≡ 𝑇

Correct Answers: D) 𝑝 ∨ ¬𝑝 ≡ 𝑇 and C) ¬𝑇 ≡ 𝐹

72. According to the Involution Law, what is ¬(¬𝑝)?

A) ¬𝑝
B) 𝑝
C) ¬(¬¬𝑝)
D) ¬(¬¬𝑝)

Correct Answer: B) 𝑝

73. Which expression is correct according to De Morgan’s Law?

A) ¬(𝑝 ∨ 𝑞) ≡ ¬𝑝 ∧ ¬𝑞
B) ¬(𝑝 ∧ 𝑞) ≡ ¬𝑝 ∧ ¬𝑞
C) ¬(𝑝 ∨ 𝑞) ≡ ¬𝑝 ∨ ¬𝑞
D) ¬(𝑝 ∧ 𝑞) ≡ ¬𝑝 ∨ ¬𝑞

Correct Answers: A) ¬(𝑝 ∨ 𝑞) ≡ ¬𝑝 ∧ ¬𝑞 and D) ¬(𝑝 ∧ 𝑞) ≡ ¬𝑝 ∨ ¬𝑞

74. What does it mean for two propositions P and Q to be logically equivalent?

A) They have the same truth value in every possible case.
B) They always have opposite truth values.
C) They are tautologies.
D) They are contradictions.

Correct Answer: A) They have the same truth value in every possible case.

75. Which symbol denotes logical equivalence between two propositions P and Q?

A) ∧
B) ∨
C) ≡
D) ¬

Correct Answer: C) ≡

76. What is the first step in testing whether two propositions P and Q are logically equivalent?

A) Construct the truth table for Q.
B) Construct the truth table for P.
C) Compare the truth values of P and Q.
D) Check if P is a tautology.

Correct Answer: B) Construct the truth table for P.

77. What must be done after constructing the truth tables for two propositions P and Q?

A) Check if both propositions are tautologies.
B) Ensure that P and Q have the same propositional variables.
C) Compare each row to see if the truth values of P and Q match.
D) Verify that P and Q are contradictions.

Correct Answer: C) Compare each row to see if the truth values of P and Q match.

78. If P and Q have the same truth values in every possible case, what can be concluded about P and Q?

A) P and Q are tautologies.
B) P and Q are contradictions.
C) P and Q are logically equivalent.
D) P and Q are mutually exclusive.

Correct Answer: C) P and Q are logically equivalent.

79. When testing for logical equivalence, why is it important to use the same propositional variables in the truth tables for P and Q?

A) To ensure that the propositions are in standard form.
B) To make sure that the comparisons are valid and accurate.
C) To avoid having too many variables in the truth tables.
D) To guarantee that the propositions are tautologies.

Correct Answer: B) To make sure that the comparisons are valid and accurate.

80. What is the significance of logical equivalence in simplifying propositions?

A) It allows the replacement of a proposition with a simpler but equivalent one.
B) It shows that propositions cannot be simplified.
C) It helps to identify contradictions within the propositions.
D) It ensures that all propositions are tautologies.

Correct Answer: A) It allows the replacement of a proposition with a simpler but equivalent one.

81. Which of the following is NOT a step in testing logical equivalence?

A) Constructing a truth table for P.
B) Constructing a truth table for Q.
C) Checking if P and Q are tautologies.
D) Comparing the truth values of P and Q.

Correct Answer: C) Checking if P and Q are tautologies.

82. What happens if the truth values of P and Q do not match in any row of their truth tables?

A) P and Q are logically equivalent.
B) P and Q are contradictions.
C) P and Q are not logically equivalent.
D) P and Q are both tautologies.

Correct Answer: C) P and Q are not logically equivalent.

83. Why might it be desirable to replace a given proposition with an equivalent one?

A) To make the proposition more complex.
B) To simplify the proposition for easier manipulation or understanding.
C) To increase the number of variables in the proposition.
D) To convert the proposition into a contradiction.

Correct Answer: B) To simplify the proposition for easier manipulation or understanding.

84. What is a tautology in propositional logic?

A) A statement pattern that is false for all possible combinations of truth values
B) A statement pattern that is neither true nor false
C) A statement pattern whose truth value is true for all possible combinations of the truth values of its prime components
D) A statement pattern that is true for some combinations of truth values and false for others

Correct Answer: C) A statement pattern whose truth value is true for all possible combinations of the truth values of its prime components

85. Which of the following is an example of a tautology?

A) P ∧ ~P
B) P ∨ ~P
C) P ∧ Q
D) P ∨ Q

Correct Answer: B) P ∨ ~P

86. What is a contradiction in propositional logic?

A) A statement pattern that is true for all possible combinations of truth values
B) A statement pattern that is neither true nor false
C) A statement pattern whose truth value is false for all possible combinations of the truth values of its prime components
D) A statement pattern that is true for some combinations of truth values and false for others

Correct Answer: C) A statement pattern whose truth value is false for all possible combinations of the truth values of its prime components

87. Which of the following is an example of a contradiction?

A) P ∨ ~P
B) P ∧ ~P
C) P ∧ Q
D) P ∨ Q

Correct Answer: B) P ∧ ~P

88. What is a contingency in propositional logic?

A) A statement pattern that is true for all possible combinations of truth values
B) A statement pattern that is false for all possible combinations of truth values
C) A statement pattern that is neither a tautology nor a contradiction
D) A statement pattern that is true for some combinations of truth values and false for others

Correct Answer: C) A statement pattern that is neither a tautology nor a contradiction

89. Which of the following is an example of a contingency?

A) P ∨ ~P
B) P ∧ ~P
C) P ∧ Q
D) ~P ∨ ~P

Correct Answer: C) P ∧ Q

90. Which logical operator is used in the statement pattern that is an example of a tautology?

A) Conjunction ( ∧ )
B) Disjunction ( ∨ )
C) Negation ( ~ )
D) Implication ( → )

Correct Answer: B) Disjunction ( ∨ )

91. Which logical operator is used in the statement pattern that is an example of a contradiction?

A) Conjunction ( ∧ )
B) Disjunction ( ∨ )
C) Negation ( ~ )
D) Implication ( → )

Correct Answer: A) Conjunction ( ∧ )

92. In propositional logic, if a statement pattern is neither always true nor always false, it is classified as:

A) Tautology
B) Contradiction
C) Contingency
D) Equivalence

Correct Answer: C) Contingency

93. Which of the following statements is not a tautology?

A) P ∨ ~P
B) P ∧ ~P
C) (P ∨ Q) ∧ (P ∨ ~Q)
D) P ∨ (P ∧ Q)